package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * author: Mr.Du
 * Date: 2023/10/7
 * Time: 11:05
 */
public class CanPartitionKSubsets {
    int sum = 0, count = 0;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        Arrays.sort(nums);

        for(int i : nums){
            sum += i;
        }
        if(sum % k != 0) return false;
        int target = sum / k;
        dfs(nums, target, 0, 0);
        return count >= k;
    }

    public void dfs(int[] nums, int target, int start, int sum){
        if(target == sum){
            count++;
            return;
        }
        if(sum > target) return;
        for(int i = start;i < nums.length;i++){
            sum += nums[i];
            dfs(nums, target, i + 1, sum);
            sum -= nums[i];
        }
    }

    public static void main(String[] args) {
        CanPartitionKSubsets canPartitionKSubsets = new CanPartitionKSubsets();
        boolean res = canPartitionKSubsets.canPartitionKSubsets(new int[]{4,3,2,3,5,2,1}, 2);
        System.out.println(res);
    }
}
